Search Results

Documents authored by Jiang, He

Found 3 Possible Name Variants:

Jiang, He

Document
DOI: 10.4230/LIPIcs.MFCS.2018.41
Low Rank Approximation of Binary Matrices: Column Subset Selection and Generalizations

Authors: Chen Dan, Kristoffer Arnsfelt Hansen, He Jiang, Liwei Wang, and Yuchen Zhou

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Low rank approximation of matrices is an important tool in machine learning. Given a data matrix, low rank approximation helps to find factors, patterns, and provides concise representations for the data. Research on low rank approximation usually focuses on real matrices. However, in many applications data are binary (categorical) rather than continuous. This leads to the problem of low rank approximation of binary matrices. Here we are given a d x n binary matrix A and a small integer k < d. The goal is to find two binary matrices U and V of sizes d x k and k x n respectively, so that the Frobenius norm of A - U V is minimized. There are two models of this problem, depending on the definition of the dot product of binary vectors: The GF(2) model and the Boolean semiring model. Unlike low rank approximation of a real matrix which can be efficiently solved by Singular Value Decomposition, we show that approximation of a binary matrix is NP-hard, even for k=1. In this paper, our main concern is the problem of Column Subset Selection (CSS), in which the low rank matrix U must be formed by k columns of the data matrix, and we are interested in the approximation ratio achievable by CSS for binary matrices. For the GF(2) model, we show that CSS has approximation ratio bounded by k/2+1+k/(2(2^k-1)) and this is asymptotically tight. For the Boolean model, it turns out that CSS is no longer sufficient to obtain a bound. We then develop a Generalized CSS (GCSS) procedure in which the columns of U are generated from Boolean formulas operating bitwise on selected columns of the data matrix. We show that the approximation ratio achieved by GCSS is bounded by 2^(k-1)+1, and argue that an exponential dependency on k is seems inherent.
Cite as

Chen Dan, Kristoffer Arnsfelt Hansen, He Jiang, Liwei Wang, and Yuchen Zhou. Low Rank Approximation of Binary Matrices: Column Subset Selection and Generalizations. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dan_et_al:LIPIcs.MFCS.2018.41,
  author =	{Dan, Chen and Hansen, Kristoffer Arnsfelt and Jiang, He and Wang, Liwei and Zhou, Yuchen},
  title =	{{Low Rank Approximation of Binary Matrices: Column Subset Selection and Generalizations}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{41:1--41:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.41},
  URN =		{urn:nbn:de:0030-drops-96239},
  doi =		{10.4230/LIPIcs.MFCS.2018.41},
  annote =	{Keywords: Approximation Algorithms, Low Rank Approximation, Binary Matrices}
}

Jiang, Zhe

Document
DOI: 10.4230/LIPIcs.ECRTS.2017.5
VCDC: The Virtualized Complicated Device Controller

Authors: Zhe Jiang and Neil Audsley

Published in: LIPIcs, Volume 76, 29th Euromicro Conference on Real-Time Systems (ECRTS 2017)

Abstract
I/O virtualization enables time and space multiplexing of I/O devices, by mapping multiple logical I/O devices upon a smaller number of physical devices. However, due to the existence of additional virtualization layers, requesting an I/O from a guest virtual machine requires complicated sequences of operations. This leads to I/O performance losses, and makes precise timing of I/O operations unpredictable. This paper proposes a hardware I/O virtualization system, termed the Virtualized Complicated Device Controller (VCDC). This I/O system allows user applications to access and operate I/O devices directly from guest VMs, and bypasses the guest OS, the Virtual Machine Monitor (VMM) and low layer I/O drivers. We show that the VCDC efficiently reduces the software overhead and enhances the I/O performance and timing predictability. Furthermore, VCDC also exhibits good scalability that can handle I/O requests from variable number of CPUs in a system.
Cite as

Zhe Jiang and Neil Audsley. VCDC: The Virtualized Complicated Device Controller. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jiang_et_al:LIPIcs.ECRTS.2017.5,
  author =	{Jiang, Zhe and Audsley, Neil},
  title =	{{VCDC: The Virtualized Complicated Device Controller}},
  booktitle =	{29th Euromicro Conference on Real-Time Systems (ECRTS 2017)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-037-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{76},
  editor =	{Bertogna, Marko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2017.5},
  URN =		{urn:nbn:de:0030-drops-71501},
  doi =		{10.4230/LIPIcs.ECRTS.2017.5},
  annote =	{Keywords: Many-core System, I/O Virtualization, Real-time I/O, Hardware Manager}
}

Jiang, Jincheng

Document
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.35
Multimodal-Transport Collaborative Evacuation Strategies for Urban Serious Emergency Incidents Based on Multi-Sources Spatiotemporal Data (Short Paper)

Authors: Jincheng Jiang, Yang Yue, and Shuai He

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
When serious emergency events happen in metropolitan cities where pedestrians and vehicles are in high-density, single modal-transport cannot meet the requirements of quick evacuations. Existing mixed modes of transportation lacks spatiotemporal collaborative ability, which cannot work together to accomplish evacuation tasks in a safe and efficient way. It is of great scientific significance and application value for emergency response to adopt multimodal-transport evacuations and improve their spatial-temporal collaboration ability. However, multimodal-transport evacuation strategies for urban serious emergency event are great challenge to be solved. The reasons lie in that: (1) large-scale urban emergency environment are extremely complicated involving many geographical elements (e.g., road, buildings, over-pass, square, hydrographic net, etc.); (2) Evacuated objects are dynamic and hard to be predicted. (3) the distributions of pedestrians and vehicles are unknown. To such issues, this paper reveals both collaborative and competitive mechanisms of multimodal-transport, and further makes global optimal evacuation strategies from the macro-optimization perspective. Considering detailed geographical environment, pedestrian, vehicle and urban rail transit, a multi-objective multi-dynamic-constraints optimization model for multimodal-transport collaborative emergency evacuation is constructed. Take crowd incidents in Shenzhen as example, empirical experiments with real-world data are conducted to evaluate the evacuation strategies and path planning. It is expected to obtain innovative research achievements on theory and method of urban emergency evacuation in serious emergency events. Moreover, this research results provide spatial-temporal decision support for urban emergency response, which is benefit to constructing smart and safe cities.
Cite as

Jincheng Jiang, Yang Yue, and Shuai He. Multimodal-Transport Collaborative Evacuation Strategies for Urban Serious Emergency Incidents Based on Multi-Sources Spatiotemporal Data (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 35:1-35:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jiang_et_al:LIPIcs.GISCIENCE.2018.35,
  author =	{Jiang, Jincheng and Yue, Yang and He, Shuai},
  title =	{{Multimodal-Transport Collaborative Evacuation Strategies for Urban Serious Emergency Incidents Based on Multi-Sources Spatiotemporal Data}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{35:1--35:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.35},
  URN =		{urn:nbn:de:0030-drops-93630},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.35},
  annote =	{Keywords: evacuation, multimodal-transport, path planning, disaster system modeling, time geography}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact